Compare and Swap(CAS)

Compare and Swap(CAS)は、同期処理機構の１つであるセマフォや、ロックフリー、ウェイトフリーなデータ構造を実装するために利用される処理である。

code:C

#include <stdint.h>

#include <stdbool.h>

bool compare_and_swap(uint64_t *p, uint64_t val, uint64_t newval)

{

if (*p != val) { // 1:*pの値がvalと異なる場合リターン

return false;

}

*p = newval; // 2:*pの値がvalと同じ場合、*pにnewvalを代入してリターン

return true;

}

上記コードはアトミックではない。

コメントをつけた二箇所は別々に実行される。

つまり、1と2の間に外部からメモリの値が変更された場合に予期しない動作になる。

このコードをコンパイルすると以下のアセンブリになる

code:x86-64

cmpq %rsi,(%rsi); rsiレジスタの値とrdiレジスタが指すメモリ上の値を比較し、結果をZFフラグに保存

jne LBBO_1 ; ZFフラグを検査し、比較結果が等しくない場合LBBO_1にジャンプ

movq %rdx,(%rdi); rdiレジスタが指すメモリ上の値を、rdxレジスタの値に書き換える

movl $1,%eax ;　eaxレジスタの値を1(True)に設定

retq ;

LBBO_1:

xorl %eax, %eax ; eaxレジスタの値を0に設定

retq ;

アセンブリコードも、概ねCでの記述に沿うように表現されており、これもアトミックではない。

このように、Cで示したコードは、アセンブリレベルにおいても通常は複数の命令を組み合わせて実行される。

これをアトミックに実行したい場合、C言語には組み込み関数として__sync_bool_compare_and_swap関数が用意されている。

code:c

#include <stdint.h>

#include <stdbool.h>

bool compare_and_swap(uint64_t *p, uint64_t val, uint64_t newval)

{

return __sync_bool_compare_and_swap(p, val, newval);

}

これをコンパイルすると、以下のようなアセンブリコードになる

code:x86-64

movq %rsi, %rsx ;rsiレジスタの値をrsxレジスタの値にコピー

xorl %ecx, %ecx ;ecxレジスタの値を0クリア

lock cmpxchgq %rdx,(%rdi);CASをアトミックに実行

sete %cl ;

movl %ecx,%eax ;ecxレジスタの値をeaxレジスタへ

retq

CAS部分を、アセンブリレベルでアトミックに記述することができた。

cmpxchgq命令をlock指定して実行することで、比較と値の交換をしている間は、外部からのメモリアクセスを排他することができる。